#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int arr[N];
int n;
bool is_prime(int x)
{
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return 0;
		}
	}
	return 1;
}
void fun()
{
	for (int i = 2; i <= N; i++) {
		if (is_prime(i)) {
			arr[i] = arr[i - 1] + 1;
		}
		else {
			arr[i] = arr[i - 1];
		}
	}
}
int main()
{
	int t;
	cin >> t;
	fun();
	/*for (int i = 1; i <= 10; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;*/
	while (t--) {
		cin >> n;
		cout << arr[n] << endl;
	}
	return 0;
}